package com.hdu.hot100.tree;

import javax.xml.soap.Node;
import java.util.*;

public class lc94 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root)
        {
            TreeNode cur = root;
            Stack<TreeNode> stack = new Stack<>();
            List<Integer> ans = new ArrayList<>();
            while (cur != null || !stack.isEmpty())
            {
                if (cur == null)
                {
                    cur = stack.pop();
                    ans.add(cur.val);
                    cur = cur.right;
                }
                else
                {
                    stack.push(cur);
                    cur = cur.left;
                }
            }
            return ans;
        }
    }
}
